troeger / fuzzed

* jsBezier-0.6

*

* Copyright (c) 2010 - 2013 Simon Porritt ([email protected])

*

* licensed under the MIT license.

* 

* a set of Bezier curve functions that deal with Beziers, used by jsPlumb, and perhaps useful for other people.  These functions work with Bezier

* curves of arbitrary degree.

*

* - functions are all in the 'jsBezier' namespace.  

* 

* - all input points should be in the format {x:.., y:..}. all output points are in this format too.

* 

* - all input curves should be in the format [ {x:.., y:..}, {x:.., y:..}, {x:.., y:..}, {x:.., y:..} ]

* 

* - 'location' as used as an input here refers to a decimal in the range 0-1 inclusive, which indicates a point some proportion along the length

* of the curve.  location as output has the same format and meaning.

* 

* 

* Function List:

* --------------

* 

* distanceFromCurve(point, curve)

* 

* 	Calculates the distance that the given point lies from the given Bezier.  Note that it is computed relative to the center of the Bezier,

* so if you have stroked the curve with a wide pen you may wish to take that into account!  The distance returned is relative to the values 

* of the curve and the point - it will most likely be pixels.

* 

* gradientAtPoint(curve, location)

* 

* 	Calculates the gradient to the curve at the given location, as a decimal between 0 and 1 inclusive.

*

* gradientAtPointAlongCurveFrom (curve, location)

*

*	Calculates the gradient at the point on the given curve that is 'distance' units from location. 

* 

* nearestPointOnCurve(point, curve) 

* 

*	Calculates the nearest point to the given point on the given curve.  The return value of this is a JS object literal, containing both the

*point's coordinates and also the 'location' of the point (see above), for example:  { point:{x:551,y:150}, location:0.263365 }.

* 

* pointOnCurve(curve, location)

* 

* 	Calculates the coordinates of the point on the given Bezier curve at the given location.  

* 		

* pointAlongCurveFrom(curve, location, distance)

* 

* 	Calculates the coordinates of the point on the given curve that is 'distance' units from location.  'distance' should be in the same coordinate

* space as that used to construct the Bezier curve.  For an HTML Canvas usage, for example, distance would be a measure of pixels.

*

* locationAlongCurveFrom(curve, location, distance)

* 

* 	Calculates the location on the given curve that is 'distance' units from location.  'distance' should be in the same coordinate

* space as that used to construct the Bezier curve.  For an HTML Canvas usage, for example, distance would be a measure of pixels.

* 

* perpendicularToCurveAt(curve, location, length, distance)

* 

* 	Calculates the perpendicular to the given curve at the given location.  length is the length of the line you wish for (it will be centered

* on the point at 'location'). distance is optional, and allows you to specify a point along the path from the given location as the center of

* the perpendicular returned.  The return value of this is an array of two points: [ {x:...,y:...}, {x:...,y:...} ].  

*  

* 

*/

(function() {

	if(typeof Math.sgn == "undefined") {

		Math.sgn = function(x) { return x == 0 ? 0 : x > 0 ? 1 :-1; };

	}

	var Vectors = {

			subtract 	: 	function(v1, v2) { return {x:v1.x - v2.x, y:v1.y - v2.y }; },

			dotProduct	: 	function(v1, v2) { return (v1.x * v2.x)  + (v1.y * v2.y); },

			square		:	function(v) { return Math.sqrt((v.x * v.x) + (v.y * v.y)); },

			scale		:	function(v, s) { return {x:v.x * s, y:v.y * s }; }

		},

		maxRecursion = 64, 

		flatnessTolerance = Math.pow(2.0,-maxRecursion-1);

	/**

	 * Calculates the distance that the point lies from the curve.

	 * 

	 * @param point a point in the form {x:567, y:3342}

	 * @param curve a Bezier curve in the form [{x:..., y:...}, {x:..., y:...}, {x:..., y:...}, {x:..., y:...}].  note that this is currently

	 * hardcoded to assume cubiz beziers, but would be better off supporting any degree. 

	 * @return a JS object literal containing location and distance, for example: {location:0.35, distance:10}.  Location is analogous to the location

	 * argument you pass to the pointOnPath function: it is a ratio of distance travelled along the curve.  Distance is the distance in pixels from

	 * the point to the curve. 

	 */

	var _distanceFromCurve = function(point, curve) {

		var candidates = [],     

	    	w = _convertToBezier(point, curve),

	    	degree = curve.length - 1, higherDegree = (2 * degree) - 1,

	    	numSolutions = _findRoots(w, higherDegree, candidates, 0),

			v = Vectors.subtract(point, curve[0]), dist = Vectors.square(v), t = 0.0;

	    for (var i = 0; i < numSolutions; i++) {

			v = Vectors.subtract(point, _bezier(curve, degree, candidates[i], null, null));

	    	var newDist = Vectors.square(v);

	    	if (newDist < dist) {

	            dist = newDist;

	        	t = candidates[i];

		    }

	    }

	    v = Vectors.subtract(point, curve[degree]);

		newDist = Vectors.square(v);

	    if (newDist < dist) {

	        dist = newDist;

	    	t = 1.0;

	    }

		return {location:t, distance:dist};

	};

	/**

	 * finds the nearest point on the curve to the given point.

	 */

	var _nearestPointOnCurve = function(point, curve) {    

		var td = _distanceFromCurve(point, curve);

	    return {point:_bezier(curve, curve.length - 1, td.location, null, null), location:td.location};

	};

	var _convertToBezier = function(point, curve) {

		var degree = curve.length - 1, higherDegree = (2 * degree) - 1,

	    	c = [], d = [], cdTable = [], w = [],

	    	z = [ [1.0, 0.6, 0.3, 0.1], [0.4, 0.6, 0.6, 0.4], [0.1, 0.3, 0.6, 1.0] ];	

	    for (var i = 0; i <= degree; i++) c[i] = Vectors.subtract(curve[i], point);

	    for (var i = 0; i <= degree - 1; i++) { 

			d[i] = Vectors.subtract(curve[i+1], curve[i]);

			d[i] = Vectors.scale(d[i], 3.0);

	    }

	    for (var row = 0; row <= degree - 1; row++) {

			for (var column = 0; column <= degree; column++) {

				if (!cdTable[row]) cdTable[row] = [];

		    	cdTable[row][column] = Vectors.dotProduct(d[row], c[column]);

			}

	    }

	    for (i = 0; i <= higherDegree; i++) {

			if (!w[i]) w[i] = [];

			w[i].y = 0.0;

			w[i].x = parseFloat(i) / higherDegree;

	    }

	    var n = degree, m = degree-1;

	    for (var k = 0; k <= n + m; k++) {

			var lb = Math.max(0, k - m),

				ub = Math.min(k, n);

			for (i = lb; i <= ub; i++) {

		    	j = k - i;

		    	w[i+j].y += cdTable[j][i] * z[j][i];

			}

	    }

	    return w;

	};

	/**

	 * counts how many roots there are.

	 */

	var _findRoots = function(w, degree, t, depth) {  

	    var left = [], right = [],	

	    	left_count, right_count,	

	    	left_t = [], right_t = [];

	    switch (_getCrossingCount(w, degree)) {

	       	case 0 : {	

	       		return 0;	

	       	}

	       	case 1 : {	

	       		if (depth >= maxRecursion) {

	       			t[0] = (w[0].x + w[degree].x) / 2.0;

	       			return 1;

	       		}

	       		if (_isFlatEnough(w, degree)) {

	       			t[0] = _computeXIntercept(w, degree);

	       			return 1;

	       		}

	       		break;

	       	}

	    }

	    _bezier(w, degree, 0.5, left, right);

	    left_count  = _findRoots(left,  degree, left_t, depth+1);

	    right_count = _findRoots(right, degree, right_t, depth+1);

	    for (var i = 0; i < left_count; i++) t[i] = left_t[i];

	    for (var i = 0; i < right_count; i++) t[i+left_count] = right_t[i];    

		return (left_count+right_count);

	};

	var _getCrossingCount = function(curve, degree) {

	    var n_crossings = 0, sign, old_sign;		    	

	    sign = old_sign = Math.sgn(curve[0].y);

	    for (var i = 1; i <= degree; i++) {

			sign = Math.sgn(curve[i].y);

			if (sign != old_sign) n_crossings++;

			old_sign = sign;

	    }

	    return n_crossings;

	};

	var _isFlatEnough = function(curve, degree) {

	    var  error,

	    	intercept_1, intercept_2, left_intercept, right_intercept,

	    	a, b, c, det, dInv, a1, b1, c1, a2, b2, c2;

	    a = curve[0].y - curve[degree].y;

	    b = curve[degree].x - curve[0].x;

	    c = curve[0].x * curve[degree].y - curve[degree].x * curve[0].y;

	    var max_distance_above = max_distance_below = 0.0;

	    for (var i = 1; i < degree; i++) {

	        var value = a * curve[i].x + b * curve[i].y + c;       

	        if (value > max_distance_above)

	            max_distance_above = value;

	        else if (value < max_distance_below)

	        	max_distance_below = value;

	    }

	    a1 = 0.0; b1 = 1.0; c1 = 0.0; a2 = a; b2 = b;

	    c2 = c - max_distance_above;

	    det = a1 * b2 - a2 * b1;

	    dInv = 1.0/det;

	    intercept_1 = (b1 * c2 - b2 * c1) * dInv;

	    a2 = a; b2 = b; c2 = c - max_distance_below;

	    det = a1 * b2 - a2 * b1;

	    dInv = 1.0/det;

	    intercept_2 = (b1 * c2 - b2 * c1) * dInv;

	    left_intercept = Math.min(intercept_1, intercept_2);

	    right_intercept = Math.max(intercept_1, intercept_2);

	    error = right_intercept - left_intercept;

	    return (error < flatnessTolerance)? 1 : 0;

	};

	var _computeXIntercept = function(curve, degree) {

	    var XLK = 1.0, YLK = 0.0,

	    	XNM = curve[degree].x - curve[0].x, YNM = curve[degree].y - curve[0].y,

	    	XMK = curve[0].x - 0.0, YMK = curve[0].y - 0.0,

	    	det = XNM*YLK - YNM*XLK, detInv = 1.0/det,

	    	S = (XNM*YMK - YNM*XMK) * detInv; 

	    return 0.0 + XLK * S;

	};

	var _bezier = function(curve, degree, t, left, right) {

	    var temp = [[]];

	    for (var j =0; j <= degree; j++) temp[0][j] = curve[j];

	    for (var i = 1; i <= degree; i++) {	

			for (var j =0 ; j <= degree - i; j++) {

				if (!temp[i]) temp[i] = [];

				if (!temp[i][j]) temp[i][j] = {};

		    	temp[i][j].x = (1.0 - t) * temp[i-1][j].x + t * temp[i-1][j+1].x;

		    	temp[i][j].y = (1.0 - t) * temp[i-1][j].y + t * temp[i-1][j+1].y;

			}

	    }    

	    if (left != null) 

	    	for (j = 0; j <= degree; j++) left[j]  = temp[j][0];

	    if (right != null)

			for (j = 0; j <= degree; j++) right[j] = temp[degree-j][j];

	    return (temp[degree][0]);

	};

	var _curveFunctionCache = {};

	var _getCurveFunctions = function(order) {

		var fns = _curveFunctionCache[order];

		if (!fns) {

			fns = [];			

			var f_term = function() { return function(t) { return Math.pow(t, order); }; },

				l_term = function() { return function(t) { return Math.pow((1-t), order); }; },

				c_term = function(c) { return function(t) { return c; }; },

				t_term = function() { return function(t) { return t; }; },

				one_minus_t_term = function() { return function(t) { return 1-t; }; },

				_termFunc = function(terms) {

					return function(t) {

						var p = 1;

						for (var i = 0; i < terms.length; i++) p = p * terms[i](t);

						return p;

					};

				};

			fns.push(new f_term());  // first is t to the power of the curve order		

			for (var i = 1; i < order; i++) {

				var terms = [new c_term(order)];

				for (var j = 0 ; j < (order - i); j++) terms.push(new t_term());

				for (var j = 0 ; j < i; j++) terms.push(new one_minus_t_term());

				fns.push(new _termFunc(terms));

			}

			fns.push(new l_term());  // last is (1-t) to the power of the curve order

			_curveFunctionCache[order] = fns;

		}

		return fns;

	};

	/**

	 * calculates a point on the curve, for a Bezier of arbitrary order.

	 * @param curve an array of control points, eg [{x:10,y:20}, {x:50,y:50}, {x:100,y:100}, {x:120,y:100}].  For a cubic bezier this should have four points.

	 * @param location a decimal indicating the distance along the curve the point should be located at.  this is the distance along the curve as it travels, taking the way it bends into account.  should be a number from 0 to 1, inclusive.

	 */

	var _pointOnPath = function(curve, location) {		

		var cc = _getCurveFunctions(curve.length - 1),

			_x = 0, _y = 0;

		for (var i = 0; i < curve.length ; i++) {

			_x = _x + (curve[i].x * cc[i](location));

			_y = _y + (curve[i].y * cc[i](location));

		}

		return {x:_x, y:_y};

	};

	var _dist = function(p1,p2) {

		return Math.sqrt(Math.pow(p1.x - p2.x, 2) + Math.pow(p1.y - p2.y, 2));

	};

	var _isPoint = function(curve) {

		return curve[0].x == curve[1].x && curve[0].y == curve[1].y;

	};

	/**

	 * finds the point that is 'distance' along the path from 'location'.  this method returns both the x,y location of the point and also

	 * its 'location' (proportion of travel along the path); the method below - _pointAlongPathFrom - calls this method and just returns the

	 * point.

	 */

	var _pointAlongPath = function(curve, location, distance) {

		if (_isPoint(curve)) {

			return {

				point:curve[0],

				location:location

			};

		}

		var prev = _pointOnPath(curve, location), 

			tally = 0, 

			curLoc = location, 

			direction = distance > 0 ? 1 : -1, 

			cur = null;

		while (tally < Math.abs(distance)) {

			curLoc += (0.005 * direction);

			cur = _pointOnPath(curve, curLoc);

			tally += _dist(cur, prev);	

			prev = cur;

		}

		return {point:cur, location:curLoc};        	

	};

	var _length = function(curve) {

		if (_isPoint(curve)) return 0;

		var prev = _pointOnPath(curve, 0),

			tally = 0,

			curLoc = 0,

			direction = 1,

			cur = null;

		while (curLoc < 1) {

			curLoc += (0.005 * direction);

			cur = _pointOnPath(curve, curLoc);

			tally += _dist(cur, prev);	

			prev = cur;

		}

		return tally;

	};

	/**

	 * finds the point that is 'distance' along the path from 'location'.  

	 */

	var _pointAlongPathFrom = function(curve, location, distance) {

		return _pointAlongPath(curve, location, distance).point;

	};

	/**

	 * finds the location that is 'distance' along the path from 'location'.  

	 */

	var _locationAlongPathFrom = function(curve, location, distance) {

		return _pointAlongPath(curve, location, distance).location;

	};

	/**

	 * returns the gradient of the curve at the given location, which is a decimal between 0 and 1 inclusive.

	 * 

	 * thanks // http://bimixual.org/AnimationLibrary/beziertangents.html

	 */

	var _gradientAtPoint = function(curve, location) {

		var p1 = _pointOnPath(curve, location),	

			p2 = _pointOnPath(curve.slice(0, curve.length - 1), location),

			dy = p2.y - p1.y, dx = p2.x - p1.x;

		return dy == 0 ? Infinity : Math.atan(dy / dx);		

	};

	/**

	returns the gradient of the curve at the point which is 'distance' from the given location.

	if this point is greater than location 1, the gradient at location 1 is returned.

	if this point is less than location 0, the gradient at location 0 is returned.

	*/

	var _gradientAtPointAlongPathFrom = function(curve, location, distance) {

		var p = _pointAlongPath(curve, location, distance);

		if (p.location > 1) p.location = 1;

		if (p.location < 0) p.location = 0;		

		return _gradientAtPoint(curve, p.location);		

	};

	/**

	 * calculates a line that is 'length' pixels long, perpendicular to, and centered on, the path at 'distance' pixels from the given location.

	 * if distance is not supplied, the perpendicular for the given location is computed (ie. we set distance to zero).

	 */

	var _perpendicularToPathAt = function(curve, location, length, distance) {

		distance = distance == null ? 0 : distance;

		var p = _pointAlongPath(curve, location, distance),

			m = _gradientAtPoint(curve, p.location),

			_theta2 = Math.atan(-1 / m),

			y =  length / 2 * Math.sin(_theta2),

			x =  length / 2 * Math.cos(_theta2);

		return [{x:p.point.x + x, y:p.point.y + y}, {x:p.point.x - x, y:p.point.y - y}];

	};

	var jsBezier = window.jsBezier = {

		distanceFromCurve : _distanceFromCurve,

		gradientAtPoint : _gradientAtPoint,

		gradientAtPointAlongCurveFrom : _gradientAtPointAlongPathFrom,

		nearestPointOnCurve : _nearestPointOnCurve,

		pointOnCurve : _pointOnPath,		

		pointAlongCurveFrom : _pointAlongPathFrom,

		perpendicularToCurveAt : _perpendicularToPathAt,

		locationAlongCurveFrom:_locationAlongPathFrom,

		getLength:_length

	};

})();

/**

 * jsPlumbGeom v0.1

 *

 * Various geometry functions written as part of jsPlumb and perhaps useful for others.

 *

 * Copyright (c) 2013 Simon Porritt

 *

 * Permission is hereby granted, free of charge, to any person

 * obtaining a copy of this software and associated documentation

 * files (the "Software"), to deal in the Software without

 * restriction, including without limitation the rights to use,

 * copy, modify, merge, publish, distribute, sublicense, and/or sell

 * copies of the Software, and to permit persons to whom the

 * Software is furnished to do so, subject to the following

 * conditions:

 *

 * The above copyright notice and this permission notice shall be

 * included in all copies or substantial portions of the Software.

 *

 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,

 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES

 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND

 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT

 * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,

 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING

 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR

 * OTHER DEALINGS IN THE SOFTWARE.

 */

;(function() {

	"use strict";

	// Establish the root object, `window` in the browser, or `global` on the server.

	var root = this;

	var jsPlumbGeom;

	if (typeof exports !== 'undefined') {

		jsPlumbGeom = exports;

	} else {

		jsPlumbGeom = root.jsPlumbGeom = {};

	}

	var _isa = function(a) { return Object.prototype.toString.call(a) === "[object Array]"; },

		_pointHelper = function(p1, p2, fn) {

		    p1 = _isa(p1) ? p1 : [p1.x, p1.y];

		    p2 = _isa(p2) ? p2 : [p2.x, p2.y];    

		    return fn(p1, p2);

		},

		/**

		* @name jsPlumbGeom.gradient

		* @function

		* @desc Calculates the gradient of a line between the two points.

		* @param {Point} p1 First point, either as a 2 entry array or object with `left` and `top` properties.

		* @param {Point} p2 Second point, either as a 2 entry array or object with `left` and `top` properties.

		* @return {Float} The gradient of a line between the two points.

		*/

		_gradient = jsPlumbGeom.gradient = function(p1, p2) {

		    return _pointHelper(p1, p2, function(_p1, _p2) { 

		        if (_p2[0] == _p1[0])

		            return _p2[1] > _p1[1] ? Infinity : -Infinity;

		        else if (_p2[1] == _p1[1]) 

		            return _p2[0] > _p1[0] ? 0 : -0;

		        else 

		            return (_p2[1] - _p1[1]) / (_p2[0] - _p1[0]); 

		    });		

		},

		/**

		* @name jsPlumbGeom.normal

		* @function

		* @desc Calculates the gradient of a normal to a line between the two points.

		* @param {Point} p1 First point, either as a 2 entry array or object with `left` and `top` properties.

		* @param {Point} p2 Second point, either as a 2 entry array or object with `left` and `top` properties.

		* @return {Float} The gradient of a normal to a line between the two points.

		*/

		_normal = jsPlumbGeom.normal = function(p1, p2) {

		    return -1 / _gradient(p1, p2);

		},

		/**

		* @name jsPlumbGeom.lineLength

		* @function

		* @desc Calculates the length of a line between the two points.

		* @param {Point} p1 First point, either as a 2 entry array or object with `left` and `top` properties.

		* @param {Point} p2 Second point, either as a 2 entry array or object with `left` and `top` properties.

		* @return {Float} The length of a line between the two points.

		*/

		_lineLength = jsPlumbGeom.lineLength = function(p1, p2) {

		    return _pointHelper(p1, p2, function(_p1, _p2) {

		        return Math.sqrt(Math.pow(_p2[1] - _p1[1], 2) + Math.pow(_p2[0] - _p1[0], 2));			

		    });

		},

		/**

		* @name jsPlumbGeom.quadrant

		* @function

		* @desc Calculates the quadrant in which the angle between the two points lies. 

		* @param {Point} p1 First point, either as a 2 entry array or object with `left` and `top` properties.

		* @param {Point} p2 Second point, either as a 2 entry array or object with `left` and `top` properties.

		* @return {Integer} The quadrant - 1 for upper right, 2 for lower right, 3 for lower left, 4 for upper left.

		*/

		_quadrant = jsPlumbGeom.quadrant = function(p1, p2) {

		    return _pointHelper(p1, p2, function(_p1, _p2) {

		        if (_p2[0] > _p1[0]) {

		            return (_p2[1] > _p1[1]) ? 2 : 1;

		        }

		        else if (_p2[0] == _p1[0]) {

		            return _p2[1] > _p1[1] ? 2 : 1;    

		        }

		        else {

		            return (_p2[1] > _p1[1]) ? 3 : 4;

		        }

		    });

		},

		/**

		* @name jsPlumbGeom.theta

		* @function

		* @desc Calculates the angle between the two points. 

		* @param {Point} p1 First point, either as a 2 entry array or object with `left` and `top` properties.

		* @param {Point} p2 Second point, either as a 2 entry array or object with `left` and `top` properties.

		* @return {Float} The angle between the two points.

		*/

		_theta = jsPlumbGeom.theta = function(p1, p2) {

		    return _pointHelper(p1, p2, function(_p1, _p2) {

		        var m = _gradient(_p1, _p2),

		            t = Math.atan(m),

		            s = _quadrant(_p1, _p2);

		        if ((s == 4 || s== 3)) t += Math.PI;

		        if (t < 0) t += (2 * Math.PI);

		        return t;

		    });

		},

		/**

		* @name jsPlumbGeom.intersects

		* @function

		* @desc Calculates whether or not the two rectangles intersect.

		* @param {Rectangle} r1 First rectangle, as a js object in the form `{x:.., y:.., w:.., h:..}`

		* @param {Rectangle} r2 Second rectangle, as a js object in the form `{x:.., y:.., w:.., h:..}`

		* @return {Boolean} True if the rectangles intersect, false otherwise.

		*/

		_intersects = jsPlumbGeom.intersects = function(r1, r2) {

		    var x1 = r1.x, x2 = r1.x + r1.w, y1 = r1.y, y2 = r1.y + r1.h,

		        a1 = r2.x, a2 = r2.x + r2.w, b1 = r2.y, b2 = r2.y + r2.h;

			return  ( (x1 <= a1 && a1 <= x2) && (y1 <= b1 && b1 <= y2) ) ||

			        ( (x1 <= a2 && a2 <= x2) && (y1 <= b1 && b1 <= y2) ) ||

			        ( (x1 <= a1 && a1 <= x2) && (y1 <= b2 && b2 <= y2) ) ||

			        ( (x1 <= a2 && a1 <= x2) && (y1 <= b2 && b2 <= y2) ) ||	

			        ( (a1 <= x1 && x1 <= a2) && (b1 <= y1 && y1 <= b2) ) ||

			        ( (a1 <= x2 && x2 <= a2) && (b1 <= y1 && y1 <= b2) ) ||

			        ( (a1 <= x1 && x1 <= a2) && (b1 <= y2 && y2 <= b2) ) ||

			        ( (a1 <= x2 && x1 <= a2) && (b1 <= y2 && y2 <= b2) );

		},

		_segmentMultipliers = [null, [1, -1], [1, 1], [-1, 1], [-1, -1] ],

		_inverseSegmentMultipliers = [null, [-1, -1], [-1, 1], [1, 1], [1, -1] ],

		/**

		* @name jsPlumbGeom.pointOnLine

		* @function

		* @desc Calculates a point on the line from `fromPoint` to `toPoint` that is `distance` units along the length of the line.

		* @param {Point} p1 First point, either as a 2 entry array or object with `left` and `top` properties.

		* @param {Point} p2 Second point, either as a 2 entry array or object with `left` and `top` properties.

		* @return {Point} Point on the line, in the form `{ x:..., y:... }`.

		*/

		_pointOnLine = jsPlumbGeom.pointOnLine = function(fromPoint, toPoint, distance) {

		    var m = _gradient(fromPoint, toPoint),

		        s = _quadrant(fromPoint, toPoint),

		        segmentMultiplier = distance > 0 ? _segmentMultipliers[s] : _inverseSegmentMultipliers[s],

		        theta = Math.atan(m),

		        y = Math.abs(distance * Math.sin(theta)) * segmentMultiplier[1],

		        x =  Math.abs(distance * Math.cos(theta)) * segmentMultiplier[0];

		    return { x:fromPoint.x + x, y:fromPoint.y + y };

		},

		/**

		* @name jsPlumbGeom.perpendicularLineTo

		* @function

		* @desc Calculates a line of length `length` that is perpendicular to the line from `fromPoint` to `toPoint` and passes through `toPoint`.

		* @param {Point} p1 First point, either as a 2 entry array or object with `left` and `top` properties.

		* @param {Point} p2 Second point, either as a 2 entry array or object with `left` and `top` properties.

		* @return {Line} Perpendicular line, in the form `[ { x:..., y:... }, { x:..., y:... } ]`.

		*/        

		_perpendicularLineTo = jsPlumbGeom.perpendicularLineTo = function(fromPoint, toPoint, length) {

		    var m = _gradient(fromPoint, toPoint),

		        theta2 = Math.atan(-1 / m),

		        y =  length / 2 * Math.sin(theta2),

		        x =  length / 2 * Math.cos(theta2);

		    return [{x:toPoint.x + x, y:toPoint.y + y}, {x:toPoint.x - x, y:toPoint.y - y}];

		};	

}).call(this);

/*

 * jsPlumb

 * 

 * Title:jsPlumb 1.5.5

 * 

 * Provides a way to visually connect elements on an HTML page, using either SVG or VML.  

 * 

 * This file contains the util functions

 *

 * Copyright (c) 2010 - 2013 Simon Porritt (http://jsplumb.org)

 * 

 * http://jsplumb.org

 * http://github.com/sporritt/jsplumb

 * http://code.google.com/p/jsplumb

 * 

 * Dual licensed under the MIT and GPL2 licenses.

 */

;(function() {

    var _isa = function(a) { return Object.prototype.toString.call(a) === "[object Array]"; },

        _isnum = function(n) { return Object.prototype.toString.call(n) === "[object Number]"; },

        _iss = function(s) { return typeof s === "string"; },

        _isb = function(s) { return typeof s === "boolean"; },

        _isnull = function(s) { return s == null; },  

        _iso = function(o) { return o == null ? false : Object.prototype.toString.call(o) === "[object Object]"; },

        _isd = function(o) { return Object.prototype.toString.call(o) === "[object Date]"; },

        _isf = function(o) { return Object.prototype.toString.call(o) === "[object Function]"; },

        _ise = function(o) {

            for (var i in o) { if (o.hasOwnProperty(i)) return false; }

            return true;

        },

        pointHelper = function(p1, p2, fn) {

            p1 = _isa(p1) ? p1 : [p1.x, p1.y];

            p2 = _isa(p2) ? p2 : [p2.x, p2.y];    

            return fn(p1, p2);

        };

    jsPlumbUtil = {        

        isArray : _isa,        

        isString : _iss,        

        isBoolean: _isb,        

        isNull : _isnull,        

        isObject : _iso,

        isDate : _isd,

        isFunction: _isf,

        isEmpty:_ise,

        isNumber:_isnum,

        clone : function(a) {

            if (_iss(a)) return "" + a;

            else if (_isb(a)) return !!a;

            else if (_isd(a)) return new Date(a.getTime());

            else if (_isf(a)) return a;

            else if (_isa(a)) {

                var b = [];

                for (var i = 0; i < a.length; i++)

                    b.push(this.clone(a[i]));

                return b;

            }

            else if (_iso(a)) {

                var c = {};

                for (var j in a)

                    c[j] = this.clone(a[j]);

                return c;		

            }

            else return a;

        },

        merge : function(a, b) {		

            var c = this.clone(a);		

            for (var i in b) {

                if (c[i] == null || _iss(b[i]) || _isb(b[i]))

                    c[i] = b[i];

                else {

                    if (_isa(b[i])/* && this.isArray(c[i])*/) {

                        var ar = [];

                        // if c's object is also an array we can keep its values.

                        if (_isa(c[i])) ar.push.apply(ar, c[i]);

                        ar.push.apply(ar, b[i]);

                        c[i] = ar;

                    }

                    else if(_iso(b[i])) {	

                        // overwite c's value with an object if it is not already one.

                        if (!_iso(c[i])) 

                            c[i] = {};

                        for (var j in b[i])

                            c[i][j] = b[i][j];

                    }

                }

            }

            return c;

        },

        copyValues:function(names, from, to) {

            for (var i = 0; i < names.length; i++)

                to[names[i]] = from[names[i]];

        },

        //

        // chain a list of functions, supplied by [ object, method name, args ], and return on the first

        // one that returns the failValue. if none return the failValue, return the successValue.

        //

        functionChain : function(successValue, failValue, fns) {        

            for (var i = 0; i < fns.length; i++) {

                var o = fns[i][0][fns[i][1]].apply(fns[i][0], fns[i][2]);

                if (o === failValue) {

                    return o;

                }

            }                

            return successValue;

        },

        // take the given model and expand out any parameters.

        populate : function(model, values) {		

            // for a string, see if it has parameter matches, and if so, try to make the substitutions.

            var getValue = function(fromString) {

                    var matches = fromString.match(/(\${.*?})/g);

                    if (matches != null) {

                        for (var i = 0; i < matches.length; i++) {

                            var val = values[matches[i].substring(2, matches[i].length - 1)];

                            if (val != null) {

                                fromString = fromString.replace(matches[i], val);

                            }

                        }							

                    }

                    return fromString;

                },		

                // process one entry.

                _one = function(d) {

                    if (d != null) {

                        if (_iss(d)) {

                            return getValue(d);

                        }

                        else if (_isa(d)) {

                            var r = [];	

                            for (var i = 0; i < d.length; i++)

                                r.push(_one(d[i]));

                            return r;

                        }

                        else if (_iso(d)) {

                            var s = {};

                            for (var j in d) {

                                s[j] = _one(d[j]);

                            }

                            return s;

                        }

                        else {

                            return d;

                        }

                    }

                };

            return _one(model);	

        },

        convertStyle : function(s, ignoreAlpha) {

            // TODO: jsPlumb should support a separate 'opacity' style member.

            if ("transparent" === s) return s;

            var o = s,

                pad = function(n) { return n.length == 1 ? "0" + n : n; },

                hex = function(k) { return pad(Number(k).toString(16)); },

                pattern = /(rgb[a]?\()(.*)(\))/;

            if (s.match(pattern)) {

                var parts = s.match(pattern)[2].split(",");

                o = "#" + hex(parts[0]) + hex(parts[1]) + hex(parts[2]);

                if (!ignoreAlpha && parts.length == 4) 

                    o = o + hex(parts[3]);

            }

            return o;

        },

        findWithFunction : function(a, f) {

            if (a)

                for (var i = 0; i < a.length; i++) if (f(a[i])) return i;

            return -1;

        },

        clampToGrid : function(x, y, grid, dontClampX, dontClampY) {

            var _gridClamp = function(n, g) { 

                var e = n % g, 

                    f = Math.floor(n / g), 

                    inc = e >= (g / 2) ? 1 : 0; 

                return (f + inc) * g; 

            };

            return [

                dontClampX || grid == null ? x : _gridClamp(x, grid[0]),

                dontClampY || grid == null ? y : _gridClamp(y, grid[1])

            ];		

        },

        indexOf : function(l, v) {

            return jsPlumbUtil.findWithFunction(l, function(_v) { return _v == v; });	

        },

        removeWithFunction : function(a, f) {

            var idx = jsPlumbUtil.findWithFunction(a, f);

            if (idx > -1) a.splice(idx, 1);

            return idx != -1;

        },

        remove : function(l, v) {

            var idx = jsPlumbUtil.indexOf(l, v);	

            if (idx > -1) l.splice(idx, 1);

            return idx != -1;

        },

        // TODO support insert index

        addWithFunction : function(list, item, hashFunction) {

            if (jsPlumbUtil.findWithFunction(list, hashFunction) == -1) list.push(item);

        },

        addToList : function(map, key, value, insertAtStart) {

            var l = map[key];

            if (l == null) {

                l = [];

                map[key] = l;

            }

            l[insertAtStart ? "unshift" : "push"](value);

            return l;

        },

        //

        // extends the given obj (which can be an array) with the given constructor function, prototype functions, and

        // class members, any of which may be null.

        //

        extend : function(child, parent, _protoFn, _protoAtts) {

            _protoFn = _protoFn || {};

            _protoAtts = _protoAtts || {};

            parent = _isa(parent) ? parent : [ parent ];            

            for (var i = 0; i < parent.length; i++) {

                for (var j in parent[i].prototype) {

                    if(parent[i].prototype.hasOwnProperty(j)) {

                        child.prototype[j] = parent[i].prototype[j];

                    }

                }

            }

            var _makeFn = function(name) {

                return function() {

                    for (var i = 0; i < parent.length; i++) {

                        if (parent[i].prototype[name])

                            parent[i].prototype[name].apply(this, arguments);

                    }                    

                    return _protoFn[name].apply(this, arguments);

                };

            };

            for (var k in _protoFn) {

                child.prototype[k] = _makeFn(k);

            }

            return child;

        },

        uuid : function() {

            return ('xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx'.replace(/[xy]/g, function(c) {

                var r = Math.random()*16|0, v = c == 'x' ? r : (r&0x3|0x8);

                return v.toString(16);

            }));

        },

        logEnabled : true,

        log : function() {

            if (jsPlumbUtil.logEnabled && typeof console != "undefined") {

                try {

                    var msg = arguments[arguments.length - 1];

                    console.log(msg);

                }

                catch (e) {} 

            }

        },

        group : function(g) { if (jsPlumbUtil.logEnabled && typeof console != "undefined") console.group(g); },

        groupEnd : function(g) { if (jsPlumbUtil.logEnabled && typeof console != "undefined") console.groupEnd(g); },

        time : function(t) { if (jsPlumbUtil.logEnabled && typeof console != "undefined") console.time(t); },

        timeEnd : function(t) { if (jsPlumbUtil.logEnabled && typeof console != "undefined") console.timeEnd(t); },

        /**

		 * helper to remove an element from the DOM.

		 */

		removeElement : function(element) {

			if (element != null && element.parentNode != null) {

				element.parentNode.removeChild(element);

			}

		},

        /**

		 * helper to remove a list of elements from the DOM.

		 */

		removeElements : function(elements) {

			for ( var i = 0; i < elements.length; i++)

				jsPlumbUtil.removeElement(elements[i]);

		},

        /*

         * Function: sizeElement 

         * Helper to size and position an element. You would typically use

         * this when writing your own Connector or Endpoint implementation.

         * 

         * Parameters: 

         *  x - [int] x position for the element origin 

         *  y - [int] y position for the element origin 

         *  w - [int] width of the element 

         *  h - [int] height of the element

         *  

         */

        sizeElement : function(el, x, y, w, h) {

            if (el) {

                el.style.height = h + "px";

                el.height = h;

                el.style.width = w + "px";

                el.width = w;

                el.style.left = x + "px";

                el.style.top = y + "px";

            }

        },

        /**

        * @name jsPlumbUtil.wrap

        * @desc Wraps one function with another, creating a placeholder for the

        * wrapped function if it was null. this is used to wrap the various

        * drag/drop event functions - to allow jsPlumb to be notified of

        * important lifecycle events without imposing itself on the user's

        * drag/drop functionality. 

        * @param {Function} wrappedFunction original function to wrap; may be null.

        * @param {Function} newFunction function to wrap the original with.

        * @param {Object} [returnOnThisValue] Optional. Indicates that the wrappedFunction should 

        * not be executed if the newFunction returns a value matching 'returnOnThisValue'.

        * note that this is a simple comparison and only works for primitives right now.

        */        

        wrap : function(wrappedFunction, newFunction, returnOnThisValue) {

            wrappedFunction = wrappedFunction || function() { };

            newFunction = newFunction || function() { };

            return function() {

                var r = null;

                try {

                    r = newFunction.apply(this, arguments);

                } catch (e) {

                    jsPlumbUtil.log("jsPlumb function failed : " + e);

                }

                if (returnOnThisValue == null || (r !== returnOnThisValue)) {

                    try {

                        r = wrappedFunction.apply(this, arguments);

                    } catch (e) {

                        jsPlumbUtil.log("wrapped function failed : " + e);

                    }

                }

                return r;

            };

        }

    };

    jsPlumbUtil.EventGenerator = function() {

        var _listeners = {}, eventsSuspended = false;

        // this is a list of events that should re-throw any errors that occur during their dispatch. as of 1.3.0 this is private to

        // jsPlumb, but it seems feasible that people might want to manipulate this list.  the thinking is that we don't want event

        // listeners to bring down jsPlumb - or do we.  i can't make up my mind about this, but i know i want to hear about it if the "ready"

        // event fails, because then my page has most likely not initialised.  so i have this halfway-house solution.  it will be interesting

        // to hear what other people think.

        var eventsToDieOn = [ "ready" ];

        this.bind = function(event, listener, insertAtStart) {

            jsPlumbUtil.addToList(_listeners, event, listener, insertAtStart);     

            return this;        

        };

        this.fire = function(event, value, originalEvent) {

            if (!eventsSuspended && _listeners[event]) {

                // instead of looping through the array we get a counter and a length, because it is possible

                // that an event fired from here could cause the object to get cleaned up, which would throw

                // away the listeners. so after each cycle through the loop we check to ensure we haven't

                // been nuked.

                var l = _listeners[event].length, i = 0, _gone = false, ret = null;

                if (!this.shouldFireEvent || this.shouldFireEvent(event, value, originalEvent)) {

                    while (!_gone && i < l && ret !== false) {                    

                        // doing it this way rather than catching and then possibly re-throwing means that an error propagated by this

                        // method will have the whole call stack available in the debugger.

                        if (jsPlumbUtil.findWithFunction(eventsToDieOn, function(e) { return e === event; }) != -1) 

                            _listeners[event][i](value, originalEvent);

                        else {

                            // for events we don't want to die on, catch and log.

                            try {                            

                                ret = _listeners[event][i](value, originalEvent);

                            } catch (e) {

                                jsPlumbUtil.log("jsPlumb: fire failed for event " + event + " : " + e);

                            }

                        }

                        i++;

                        if (_listeners == null || _listeners[event] == null) _gone = true;                    

                    }

                }

            }

            return this;

        };

        this.unbind = function(event) {

            if (event)

                delete _listeners[event];

            else {

                _listeners = {};

            }

            return this;

        };

        this.getListener = function(forEvent) {

            return _listeners[forEvent];

        };              

        this.setSuspendEvents = function(val) {

            eventsSuspended = val;    

        };        

        this.isSuspendEvents = function() {

            return eventsSuspended;

        };        

        this.cleanupListeners = function() {

            for (var i in _listeners) {

                _listeners[i].splice(0);

                delete _listeners[i];

            }

        };

    };

    jsPlumbUtil.EventGenerator.prototype = {

        cleanup:function() {

            this.cleanupListeners();

        }

    };

    // thanks MDC

    // https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Function/bind?redirectlocale=en-US&redirectslug=JavaScript%2FReference%2FGlobal_Objects%2FFunction%2Fbind

    if (!Function.prototype.bind) {

      Function.prototype.bind = function (oThis) {

        if (typeof this !== "function") {

          // closest thing possible to the ECMAScript 5 internal IsCallable function

          throw new TypeError("Function.prototype.bind - what is trying to be bound is not callable");

        }

        var aArgs = Array.prototype.slice.call(arguments, 1), 

            fToBind = this, 

            fNOP = function () {},

            fBound = function () {

              return fToBind.apply(this instanceof fNOP && oThis ? this : oThis,

                                   aArgs.concat(Array.prototype.slice.call(arguments)));

            };

        fNOP.prototype = this.prototype;

        fBound.prototype = new fNOP();

        return fBound;

      };

    }

})();

/*

 * jsPlumb

 * 

 * Title:jsPlumb 1.5.5

 * 

 * Provides a way to visually connect elements on an HTML page, using either SVG, Canvas

 * elements, or VML.  

 * 

 * This file contains the base functionality for DOM type adapters. 

 *

 * Copyright (c) 2010 - 2013 Simon Porritt (http://jsplumb.org)

 * 

 * http://jsplumb.org

 * http://github.com/sporritt/jsplumb

 * http://code.google.com/p/jsplumb

 * 

 * Dual licensed under the MIT and GPL2 licenses.

 */

;(function() {

		var canvasAvailable = !!document.createElement('canvas').getContext,

		svgAvailable = !!window.SVGAngle || document.implementation.hasFeature("http://www.w3.org/TR/SVG11/feature#BasicStructure", "1.1"),

		// http://stackoverflow.com/questions/654112/how-do-you-detect-support-for-vml-or-svg-in-a-browser

		vmlAvailable = function() {		    

            if (vmlAvailable.vml === undefined) { 

                var a = document.body.appendChild(document.createElement('div'));

            	a.innerHTML = '<v:shape id="vml_flag1" adj="1" />';

            	var b = a.firstChild;

            	if (b != null && b.style != null) {

	            	b.style.behavior = "url(#default#VML)";

	            	vmlAvailable.vml = b ? typeof b.adj == "object": true;

	            }

	            else

	            	vmlAvailable.vml = false;

            	a.parentNode.removeChild(a);

            }

            return vmlAvailable.vml;

		};

    /**

		Manages dragging for some instance of jsPlumb.

	*/

	var DragManager = function(_currentInstance) {		

		var _draggables = {}, _dlist = [], _delements = {}, _elementsWithEndpoints = {},			

			// elementids mapped to the draggable to which they belong.

			_draggablesForElements = {};			

        /**

            register some element as draggable.  right now the drag init stuff is done elsewhere, and it is

            possible that will continue to be the case.

        */

		this.register = function(el) {

            var jpcl = jsPlumb.CurrentLibrary,

            	_el = jpcl.getElementObject(el),

            	id = _currentInstance.getId(el),                

                parentOffset = jpcl.getOffset(_el);

            if (!_draggables[id]) {

                _draggables[id] = el;